package Algorithm.sort.basic;

import java.util.Arrays;

/**
 * 计数排序：扫描统计出待排序数组中每个元素出现的次数存储在辅助数组对应下标位置（下标+固定偏置=元素值）中，最后扫描这个辅助数组，从每个位置取出对应次数的元素，即构成有序序列。
 *
 * **性能**：时间复杂度为O(n+k)，k为辅助数组的长度，即待排序数组最大元素值减去最小元素值再加1。空间复杂度为O(k)。
 *
 * **适用场景**：待排序数组的数据范围较小的场景
 */
public class CountSort {

    public static void main(String[] args) {
        int[] A = new int[]{5,6,1,2,3,6,9};
        countSort(A);
        System.out.println(Arrays.toString(A));
    }

    static void countSort(int[] A) {
        int min=A[0], max=A[0];
        //在一次遍历中同时寻找最小元素和最大元素
        for (int i=1;i < A.length;i++) {
            if (min > A[i])
                min = A[i];
            if (max < A[i])
                max = A[i];
        }
        int[] B = new int[max-min+1]; //辅助数组
        for (int i=0;i < A.length;i++) {
            int index = A[i] - min; //元素A[i]在统计数组中对应的下标
            B[index] = B[index] + 1; //元素A[i]出现次数增1
        }
        //扫描辅助数组
        for (int k=0,i=0;k < B.length;k++) {
            for (int j=1;j <= B[k];j++) {
                A[i++] = k+min;
            }
        }
    }
}
/**
 * **简评**：当待排序数组的数据范围较小时，计数排序速度非常之快，但对于数据范围很大的数组，就需要大量时间和内存了。显然计数排序也是一种可以进行外部排序的算法
 */